//给你一个points 数组，表示 2D 平面上的一些点，其中 points[i] = [xi, yi] 。 
//
// 连接点 [xi, yi] 和点 [xj, yj] 的费用为它们之间的 曼哈顿距离 ：|xi - xj| + |yi - yj| ，其中 |val| 表示 
//val 的绝对值。 
//
// 请你返回将所有点连接的最小总费用。只有任意两点之间 有且仅有 一条简单路径时，才认为所有点都已连接。 
//
// 
//
// 示例 1： 
//
// 
//
// 
//输入：points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
//输出：20
//解释：
//
//我们可以按照上图所示连接所有点得到最小总费用，总费用为 20 。
//注意到任意两个点之间只有唯一一条路径互相到达。
// 
//
// 示例 2： 
//
// 
//输入：points = [[3,12],[-2,5],[-4,1]]
//输出：18
// 
//
// 示例 3： 
//
// 
//输入：points = [[0,0],[1,1],[1,0],[-1,1]]
//输出：4
// 
//
// 示例 4： 
//
// 
//输入：points = [[-1000000,-1000000],[1000000,1000000]]
//输出：4000000
// 
//
// 示例 5： 
//
// 
//输入：points = [[0,0]]
//输出：0
// 
//
// 
//
// 提示： 
//
// 
// 1 <= points.length <= 1000 
// -10⁶ <= xi, yi <= 10⁶ 
// 所有点 (xi, yi) 两两不同。 
// 
// Related Topics并查集 | 数组 | 最小生成树 
//
// 👍 219, 👎 0 
//
//
//
//

package leetcode.editor.cn;

import java.util.*;

class MinCostToConnectAllPoints {
    public static void main(String[] args) {
        Solution solution = new MinCostToConnectAllPoints().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        // 参照labuladong：https://mp.weixin.qq.com/s/dJ9gqR3RVoeGnATlpMG39w
        // Kruskal算法实现
        /*public int minCostConnectPoints(int[][] points) {
            int n = points.length;
            List<int[]> edges = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                for (int j = i + 1; j < n; j++) {
                    int x1 = points[i][0], y1 = points[i][1];
                    int x2 = points[j][0], y2 = points[j][1];
                    int weight = Math.abs(x1 - x2) + Math.abs(y1 - y2);

                    edges.add(new int[]{i, j, weight});
                }
            }

            // 将权重从小到大排序
            Collections.sort(edges, (a, b) -> a[2] - b[2]);

            UF uf = new UF(n);
            int mst = 0;
            for (int[] edge : edges) {
                int from = edge[0], to = edge[1], weight = edge[2];
                if (uf.connected(from, to)) continue;
                uf.union(from, to);
                mst += weight;
            }

            return mst;
        }

        class UF {
            private int count;
            private int[] parent;

            public UF(int n) {
                this.count = n;
                parent = new int[n];
                for (int i = 0; i < n; i++) {
                    parent[i] = i;
                }
            }

            public int count() {
                return count;
            }

            public int find(int x) {
                if (parent[x] != x) {
                    parent[x] = find(parent[x]);
                }

                return parent[x];
            }

            public boolean connected(int p, int q) {
                int rootP = find(p);
                int rootQ = find(q);
                return rootP == rootQ;
            }

            public void union(int p, int q) {
                int rootP = find(p);
                int rootQ = find(q);
                if (rootP == rootQ) return;

                parent[rootP] = rootQ;
                count--;
            }

        }*/

        public int minCostConnectPoints(int[][] points) {
            List<int[]>[] graph = buildGraph(points.length, points);
            Prim prim = new Prim(graph);
            return prim.weightSum();
        }

        public List<int[]>[] buildGraph(int n, int[][] points) {
            LinkedList<int[]>[] graph = new LinkedList[n];
            for (int i = 0; i < n; i++) {
                graph[i] = new LinkedList<>();
            }

            for (int i = 0; i < n; i++) {
                for (int j = i + 1; j < n; j++) {
                    int from1 = points[i][0], to1 = points[i][1];
                    int from2 = points[j][0], to2 = points[j][1];
                    int weight = Math.abs(from1 - from2) + Math.abs(to1 - to2);
                    graph[i].add(new int[]{i, j, weight});
                    graph[j].add(new int[]{j, i, weight});
                }
            }

            return graph;
        }

        // Prim算法实现
        class Prim {
            // 核心数据结构，存储「横切边」的优先级队列
            private PriorityQueue<int[]> pq;
            // 类似 visited 数组的作用，记录哪些节点已经成为最小生成树的一部分
            private boolean[] inMST;
            // 记录最小生成树的权重和
            private int weightSum;
            // graph 是用邻接表表示的一幅图，
            // graph[s] 记录节点 s 所有相邻的边，
            // 三元组 int[]{from, to, weight} 表示一条边
            private List<int[]>[] graph;

            public Prim(List<int[]>[] graph) {
                this.graph = graph;
                // 按照权重从小到大排序
                pq = new PriorityQueue<>((a, b) -> a[2] - b[2]);
                int n = graph.length;
                inMST = new boolean[n];

                // 随机选择一个节点
                cut(0);
                inMST[0] = true;

                while (!pq.isEmpty()) {
                    int[] poll = pq.poll();
                    int to = poll[1], weight = poll[2];

                    if (inMST[to]) {
                        // 节点 to 已经在最小生成树中，跳过
                        // 否则这条边会产生环
                        continue;
                    }

                    weightSum += weight;
                    inMST[to] = true;
                    cut(to);
                }
            }

            // 将 s 的横切边加入优先队列
            private void cut(int s) {
                // 遍历 s 的邻边
                for (int[] edge : graph[s]) {
                    int to = edge[1];
                    // 存在重复的，不再加入
                    if (inMST[to]) {
                        continue;
                    }

                    // 加入横切边队列
                    pq.offer(edge);
                }
            }

            // 最小生成树的权重和
            public int weightSum() {
                return weightSum;
            }

            // 判断最小生成树是否包含图中的所有节点
            public boolean allConnected() {
                for (int i = 0; i < inMST.length; i++) {
                    if (!inMST[i]) {
                        return false;
                    }
                }
                return true;
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
